#leetcode题目19：删除链表的倒数第N个结点
#难度：中等
#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：核心思想，快慢指针，快指针先走n步，然后慢指针和快指针一起走，当快指针走到链表末尾时，慢指针就是倒数第n个结点。
from typing import List
class ListNode:
    def __init__(self, data):
        self.val = data
        self.next = None


#TODO 链表类，注意在leetcode中没有这个，纯粹是acm模式下才需要这个
class LinkList:
    def __init__(self):
        self.head = None

    def initList(self, data):
        if not data:
            return None
        
        # 创建头结点
        self.head = ListNode(data[0])
        r = self.head
        p = self.head
        
        # 逐个为 data 内的数据创建结点,建立链表
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r

    def printlist(self, head):
        if head == None:
            return
        node = head
        while node != None:
            print(node.val, end=' ')
            node = node.next
        print()  # 换行

#核心解法  
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy=ListNode(0)
        dummy.next=head
        slow=dummy
        fast=dummy
        #快指针先走n步
        for i in range(n):
            fast=fast.next
        #慢指针和快指针一起走
        while fast.next:
            slow=slow.next
            fast=fast.next
        #删除倒数第n个结点
        slow.next=slow.next.next
        return dummy.next 

#测试数据
data=[1,2,3,4,5]
head=LinkList().initList(data)
n=2 #n是val值，表示倒数第二个数
#预期输出：[1,2,3,5]
solution=Solution()

LinkList().printlist(solution.removeNthFromEnd(head,n))


